package com.example.algorithm.AList;

import java.util.LinkedList;

/**
 * @author: dangwen
 * @createDate: 2021/7/4
 * 239.求滑动窗口中的最大值
 */
public class MaxSlideWindow {

    public static int[] slideWindow(int[] arr, int k){
        int[] result = new int[arr.length-k + 1];
        LinkedList<Integer> linkedList = new LinkedList<>();
        for (int right = 0; right < arr.length; right++) {
            while (!linkedList.isEmpty() && arr[linkedList.peekLast()] < arr[right]){
                linkedList.pollLast();
            }
            linkedList.addLast(right);
            int left = right - k + 1;
            if(linkedList.peekFirst() < left){
                linkedList.pollFirst();
            }
            if(right + 1 >= k){
                result[left] = arr[linkedList.peekFirst()];
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1,3,-1,-3,5,3,6,7};
        int[] ints = slideWindow(nums, 3);
        for (int i:
             ints) {
            System.out.println(i);
        }
    }
}
